package _greedy;

import org.junit.Assert;
import org.junit.Test;

/*
题型：动态规划 / 贪心算法

https://leetcode.cn/problems/integer-break/description/
https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html#%E6%80%9D%E8%B7%AF

343. 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 */
public class leetcode_343 {
    @Test
    public void test_1() {
        int actual = integerBreak(2);
        int expect = 1;
        Assert.assertEquals(expect, actual);
    }

    @Test
    public void test_2() {
        int actual = integerBreak(10);
        int expect = 36;
        Assert.assertEquals(expect, actual);
    }

    @Test
    public void test_others() {
        int actual = integerBreak(10);
        int expect = 36;
        Assert.assertEquals(expect, actual);
    }

    public int integerBreak(int n) {
//        return integerBreak1(n);
        return integerBreak2(n);
    }
    public int integerBreak1(int n) {
        // 动态规划

        // 1 数组，将k拆后的乘积最大值
        // 2 递推公式  dp[i]= max(d[[i]],  j * (i-j), j * dp(i-j)),i>=3
        // 3 初始化 dp[i] = 2
        // 4 遍历
        // 5 打印

        int[] dp = new int[n + 1];
        dp[2] = 2;

        if (n == 2) {
            return 1;
        }

        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                // System.out.println("[0]j * (i - j)="+(j * (i - j)));
                // System.out.println("[1]j * dp[i-j]="+(j * dp[i-j]));
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                // System.out.println("[2]dp[i]="+(dp[i]));
            }
        }
        return dp[n];
    }

    public int integerBreak2(int n) {
        /**
         * 贪心算法
         * 规律：
         * n = 2 => 1 * 1
         * n = 3 => 2 * 1 = 2
         * n = 4 => 3 * 1 = 3
         * n > 4
         * n = 5 => 3 * 2 = 6
         * n = 6 => 3 * 3 = 9
         * n = 7 => 3 * 4 = 12
         * n = 8 => 3 * 3 * 2 = 18
         * 规律：n > 4 时，最大乘积  = 3 * 3 * 3 * num, num <= 4
         */
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 3;

        int result = 1;
        int num = n;
        while (num > 4) {
            result = result * 3;
            num = num - 3;
        }
        System.err.println("num = " + num);
//        if (num > 0) {
            result = result * num;
//        }
        return result;
    }
}
